﻿//https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        int n = heights.size();
        vector<int> left(n), right(n, n);  //确定每一个柱状图的左边界和有边界
        stack<int> st;
        //找左端点
        for (int i = 0; i < n; i++)
        {
            while (!st.empty() && heights[st.top()] >= heights[i])
            {
                //遍历的时候就收集右端点
                right[st.top()] = i;
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }

        // //找右端点
        // st = stack<int>();  //匿名对象
        // for(int i=n-1;i>=0;i--)
        // {
        //     while(!st.empty()&&heights[st.top()]>=heights[i])
        //     {
        //         st.pop();
        //     }
        //     right[i]=st.empty()?n:st.top();
        //     st.push(i);
        // }

        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            ret = max(ret, heights[i] * (right[i] - left[i] - 1));
        }

        return ret;

    }
};